#include <stdio.h>
#include <stdlib.h>

// 定义链表节点
typedef int elementType;

typedef struct lnode {
    elementType data; 
    struct lnode *next; 
} Lnode, *LinkList;

// 创建链表
LinkList createList(int n) {
    LinkList head = (LinkList)malloc(sizeof(Lnode));
    head->next = NULL;
    
    Lnode *current = head;
    for (int i = 0; i < n; i++) {
        Lnode *newNode = (Lnode *)malloc(sizeof(Lnode));
        scanf("%d", &newNode->data);
        newNode->next = NULL;
        current->next = newNode;
        current = newNode;
    }
    
    return head;
}

// 插入元素到有序链表中
void insertList(LinkList head, elementType value) {
    Lnode *newNode = (Lnode *)malloc(sizeof(Lnode));
    newNode->data = value;
    
    Lnode *current = head;
    while (current->next != NULL && current->next->data < value) {
        current = current->next;
    }
    
    newNode->next = current->next;
    current->next = newNode;
}

// 输出链表
void printList(LinkList head) {
    Lnode *current = head->next; // 从第一个元素开始
    while (current != NULL) {
        printf(" %d", current->data);
        current = current->next;
    }
    printf("\n");
}

int main() {
    int n;
    scanf("%d", &n);
   
    // 创建链表  
    LinkList list = createList(n);
    
    // 读取待插入的元素
    elementType value;
    scanf("%d", &value);
    
    // 插入元素
    insertList(list, value);
    
    // 输出链表
    printList(list);
    
    // 释放内存
    Lnode *current = list;
    while (current != NULL) {
        Lnode *temp = current;
        current = current->next;
        free(temp);
    }

    return 0;
}
